# 入参需要start起点、end终点、graph相邻节点以字典方式传入
from string import digits
import copy

def getChars(length):
    return [getChar(index) for index in range(length)]

def getChar(number):
    factor, moder = divmod(number, 26)
    modChar = chr(moder + 65)
    if factor != 0:
        modChar = getChar(factor-1) + modChar
    return modChar

def createrule(graph):#创建节点转换对应规则
    lack=[]
    all=[]
    rule={}
    for key in graph:
        if key not in all:
            all.append(key)
        for i in graph[key]:
            if i not in graph.keys():
                lack.append(i)
            if i not in all:
                all.append(i)
    for i in lack:
        graph[i]=[]
    zhuanhuan=getChars(len(all))
    for i in all:
        rule[i]=zhuanhuan[all.index(i)]
    return rule
def pointtran(start,end,rule):#起点和终点转换
    startnew=[]
    endnew=[]
    for i in start:
        startnew.append(rule[i])
    for i in end:
        endnew.append(rule[i])
    return startnew,endnew
def graphupdate(graph,rule): #转换有多个转入方向的节点
    count = {}
    graphtran = {}
    for key in graph:
        graphtran[rule[key]]=[]
        for i in graph[key]:
            graphtran[rule[key]].append(rule[i])
    graphnew = copy.deepcopy(graphtran)
    for key in graphtran:
        count[key] = 0
    for key in graphtran:
        for i in graphtran[key]:
            count[i] = count[i] + 1
            if count[i] > 1:
                xuhao = i + str(count[i] - 1)
                graphnew[key][graphnew[key].index(i)] = xuhao
                graphnew[xuhao] = graphtran[i]
    #print(graphnew)
    return graphnew
def findAllPath(graph, start, end, path=[]):#导出单个节点为起点和终点的所有路径
    remove_digits = str.maketrans('', '', digits)
    for key in graph:
        for i in graph[key]:
            if end in i:
                graph[key][graph[key].index(i)]=i.translate(remove_digits)#去除终点的数字，保证终点唯一
    path = path + [start]
    if start == end:
        return [path]
    paths = []  # 存储所有路径
    for node in graph[start]:
        if node not in path:
            newpaths = findAllPath(graph, node, end, path)
            for newpath in newpaths:
                for i in range(len(newpath)):
                    newpath[i]= newpath[i].translate(remove_digits)
                paths.append(newpath)
    return paths
def shaixuan(allpath): #筛选路径
    paths=[]#记录保留的路径
    pathspaixu=[]
    bianli=[]#记录遍历的节点
    baoliu=[]#记录保留的路径标号
    longest=0#记录最长的路径长度
    longflag=0#记录最长路径的标号
    finalresult=[]
    allpath = selectedSort(allpath)
    for i in range(len(allpath)):
        compath=[]
        if len(allpath[i])>longest:
            longest=len(allpath[i])
            longflag=i
        for t in range(len(allpath[i])-1):
            compath.append([allpath[i][t], allpath[i][t+1]])
        paths.append(compath)
    baoliu.append(longflag)
    for t in range(len(paths[longflag])):
        bianli.append(paths[longflag][t])
    for i in range(len(paths)):
        for t in range(len(paths[i])):
            if paths[i][t] not in bianli:
                if i not in baoliu:
                    baoliu.append(i)
                bianli.append(paths[i][t])
    for i in baoliu:
        finalresult.append(allpath[i])
    return finalresult
def selectedSort(myList):#将路径按节点多少排序
    #获取list的长度
    length = len(myList)
    #一共进行多少轮比较
    for i in range(0,length-1):
        #默认设置最小值得index为当前值
        smallest = i
        #用当先最小index的值分别与后面的值进行比较,以便获取最小index
        for j in range(i+1,length):
            #如果找到比当前值小的index,则进行两值交换
            if len(myList[j])<len(myList[smallest]):
                tmp = myList[j]
                myList[j] = myList[smallest]
                myList[smallest]=tmp
        #打印每一轮比较好的列表
    return myList
def getkey(dct, value):#根据字典值获取键值
    return list(filter(lambda k:dct[k] == value, dct))
def getallpath(start,end,graph):
    pathtotal=[]
    allpath=[]
    rule=createrule(graph)
    startlist,endlist=pointtran(start,end,rule)
    for startpoint in startlist:
        for endpoint in endlist:
            pathtotal.append(findAllPath(graphupdate(graph,rule), startpoint, endpoint))
    for i in pathtotal:
        for path in i:
            pathnew=[]
            for point in path:
                pathnew.append(getkey(rule,point)[0])
            allpath.append(pathnew)
    return allpath

